package leetcode.day_2020_11_9_11_15;

public class L_23 {

    public ListNode mergeKLists(ListNode[] lists) {
        ListNode root = new ListNode(-1);
        for (int i = 0; i < lists.length; ++i) {
            root = mergeList(root, lists[i]);
        }
        return root;
    }

    public ListNode mergeList(ListNode a, ListNode b) {
        if(a==null || b==null) {
            return a!=null ? a : b;
        }
        ListNode root = new ListNode(-1);
        ListNode curr = root;
        ListNode currA = a;
        ListNode currB = b;
        while (currA!=null && currB!=null) {
            if (currA.val <= currB.val) {
                curr.next = currA;
                currA = currA.next;
                curr = curr.next;
            } else {
                curr.next = currB;
                currB = currB.next;
                curr = curr.next;
            }
             curr.next = currA!=null ? currA:currB;
        }
        return root.next;
    }
}
